package com.sheng.leetcode.year2023.month04.day28;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2023/04/28
 * <p>
 * 1172. 餐盘栈<p>
 * <p>
 * 我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。<p>
 * 实现一个叫「餐盘」的类 DinnerPlates：<p>
 * DinnerPlates(int capacity) - 给出栈的最大容量 capacity。<p>
 * void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。<p>
 * int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。<p>
 * int popAtStack(int index) - 返回编号 index 的栈顶部的值，<p>
 * 并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。<p>
 * <p>
 * 示例：<p>
 * 输入： <p>
 * ["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]<p>
 * [[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]<p>
 * 输出：<p>
 * [null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]<p>
 * 解释：<p>
 * DinnerPlates D = DinnerPlates(2);  // 初始化，栈最大容量 capacity = 2<p>
 * D.push(1);<p>
 * D.push(2);<p>
 * D.push(3);<p>
 * D.push(4);<p>
 * D.push(5);<p>
 * // 栈的现状为：<p>
 *   2  4<p>
 * 1  3  5<p>
 * ﹈ ﹈ ﹈<p>
 * D.popAtStack(0);<p>
 * // 返回 2。栈的现状为：<p>
 *         4<p>
 * 1   3   5<p>
 * ﹈ ﹈ ﹈<p>
 * D.push(20);<p>
 * // 栈的现状为：<p>
 *   20  4<p>
 * 1   3   5<p>
 * ﹈ ﹈ ﹈<p>
 * D.push(21);<p>
 * // 栈的现状为：<p>
 *   20  4 21<p>
 * 1   3   5<p>
 * ﹈ ﹈ ﹈<p>
 * D.popAtStack(0);<p>
 * // 返回 20。栈的现状为：<p>
 *         4 21<p>
 * 1   3   5<p>
 * ﹈ ﹈ ﹈<p>
 * D.popAtStack(2);<p>
 * // 返回 21。栈的现状为：<p>
 *         4<p>
 * 1   3   5<p>
 * ﹈ ﹈ ﹈<p>
 * D.pop()<p>
 * // 返回 5。栈的现状为：<p>
 *         4<p>
 * 1   3<p>
 * ﹈ ﹈<p>
 * D.pop()<p>
 * // 返回 4。栈的现状为：<p>
 * 1   3<p>
 * ﹈ ﹈<p>
 * D.pop()<p>
 * // 返回 3。栈的现状为：<p>
 *    1<p>
 * ﹈<p>
 * D.pop()            // 返回 1。现在没有栈。<p>
 * D.pop()            // 返回 -1。仍然没有栈。<p>
 * <p>
 * 提示：<p>
 * 1 <= capacity <= 20000<p>
 * 1 <= val <= 20000<p>
 * 0 <= index <= 100000<p>
 * 最多会对 push，pop，和 popAtStack 进行 200000 次调用。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/dinner-plate-list">1172. 餐盘栈</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1172 {

    @Test
    public void test01() {
        DinnerPlates obj = new DinnerPlates(2);
        obj.push(1);
        obj.push(2);
        obj.push(3);
        obj.push(4);
        obj.push(5);
        System.out.println(obj.popAtStack(0)); // 2
        obj.push(20);
        obj.push(21);
        System.out.println(obj.popAtStack(0)); // 20
        System.out.println(obj.popAtStack(2)); // 21
        System.out.println(obj.pop()); // 5
        System.out.println(obj.pop()); // 4
        System.out.println(obj.pop()); // 3
        System.out.println(obj.pop()); // 1
        System.out.println(obj.pop()); // -1
    }
}

class DinnerPlates {

    int capacity;
    List<Deque<Integer>> list = new ArrayList<>();
    TreeSet<Integer> set = new TreeSet<>();

    /**
     * 给出栈的最大容量 capacity
     *
     * @param capacity 餐盘栈的最大容量
     */
    public DinnerPlates(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 将给出的正整数 val 推入 从左往右第一个 没有满的栈
     *
     * @param val val
     */
    public void push(int val) {
        if (set.isEmpty()) {
            list.add(new ArrayDeque<>());
            list.get(list.size() - 1).push(val);
            if (capacity > 1) {
                set.add(list.size() - 1);
            }
        } else {
            int index = set.first();
            list.get(index).push(val);
            if (list.get(index).size() == capacity) {
                set.pollFirst();
            }
        }
    }

    /**
     * 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1
     *
     * @return 返回值 / -1
     */
    public int pop() {
        return popAtStack(list.size() - 1);
    }

    /**
     * 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1
     *
     * @param index 编号
     * @return 返回值 / -1
     */
    public int popAtStack(int index) {
        if (index < 0 || index >= list.size() || list.get(index).isEmpty()) {
            return -1;
        }
        int val = list.get(index).pop();
        if (index == list.size() - 1 && list.get(list.size() - 1).isEmpty()) {
            while (!list.isEmpty() && list.get(list.size() - 1).isEmpty()) {
                set.remove(list.size() - 1);
                list.remove(list.size() - 1);
            }
        } else {
            set.add(index);
        }
        return val;
    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates obj = new DinnerPlates(capacity);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAtStack(index);
 */
